{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T04:49:58.777403Z",
     "start_time": "2018-12-19T04:49:57.319669Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Authorization for Minor Form.rtf\n",
      "child_wishlist_v2.csv\n",
      "gift_goodkids_v2.csv\n",
      "sample_submission_random_v2.csv\n",
      "\n"
     ]
    }
   ],
   "source": [
    "import numpy as np # linear algebra\n",
    "import pandas as pd # data processing, CSV file I/O (e.g. pd.read_csv)\n",
    "import math\n",
    "from collections import Counter\n",
    "from subprocess import check_output\n",
    "#看看文件是否存在，并且是不是用utf8\n",
    "print(check_output([\"ls\", \"input\"]).decode(\"utf8\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 后面看懂代码后改成dataframe\n",
    "```python\n",
    "drop(0,1)的意思是：其中1表示axis=1,0表示名称，在这里即为删除名称为0的列\n",
    "gift_pref_df = pd.read_csv('../input/child_wishlist_v2.csv',header=None).drop(0,1)\n",
    "child_pref_df = pd.read_csv('../input/gift_goodkids_v2.csv',header=None).drop(0,1)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T04:50:23.526942Z",
     "start_time": "2018-12-19T04:50:02.515479Z"
    }
   },
   "outputs": [],
   "source": [
    "#居然转换成了ndarry\n",
    "#孩子喜欢的礼物\n",
    "gift_pref = pd.read_csv('input/child_wishlist_v2.csv',header=None).drop(0, 1).values\n",
    "#礼物喜欢的孩子\n",
    "child_pref = pd.read_csv('input/gift_goodkids_v2.csv',header=None).drop(0, 1).values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T05:19:26.432711Z",
     "start_time": "2018-12-19T05:19:26.414840Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "numpy.ndarray"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(child_pref)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T05:19:28.707485Z",
     "start_time": "2018-12-19T05:19:28.453176Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "999\n"
     ]
    }
   ],
   "source": [
    "print(np.min(gift_pref))\n",
    "print(np.max(gift_pref))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T05:19:30.397491Z",
     "start_time": "2018-12-19T05:19:30.388900Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "999999\n"
     ]
    }
   ],
   "source": [
    "print(np.min(child_pref))\n",
    "print(np.max(child_pref))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-13T12:59:24.803487Z",
     "start_time": "2018-12-13T12:59:01.036617Z"
    }
   },
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T05:19:33.896851Z",
     "start_time": "2018-12-19T05:19:33.889497Z"
    }
   },
   "outputs": [],
   "source": [
    "#有1000000个children\n",
    "n_children = 1000000 \n",
    "#1000种gift\n",
    "n_gift_type = 1000\n",
    "#每种gift1000个\n",
    "n_gift_quantity = 1000 \n",
    "#每个孩子有喜欢的100个礼物。(孩子开心)\n",
    "n_gift_pref = 100 # number of gifts a child ranks\n",
    "#每个礼物优先考虑1000个好孩子（圣诞老人开心）\n",
    "n_child_pref = 1000 # number of children a gift ranks\n",
    "#0-5000为三胞胎，triplets=50001 0.5%\n",
    "triplets = math.ceil(0.005 * n_children / 3.) * 3    \n",
    "#5001-45000双胞胎，即45000-5001+1=40000\n",
    "twins = math.ceil(0.04 * n_children / 2.) * 2    \n",
    "#根据目标函数里面定义的\n",
    "ratio_gift_happiness = 2\n",
    "ratio_child_happiness = 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T05:19:36.809351Z",
     "start_time": "2018-12-19T05:19:36.799733Z"
    }
   },
   "outputs": [],
   "source": [
    "#非双胞胎和非三胞胎的孩子，因为成pair，因此-6只是占位符\n",
    "class Child(object):\n",
    "    \n",
    "    def __init__(self, idx, prefer):\n",
    "        \n",
    "        self.idx = idx\n",
    "        self.prefer_dict = dict()\n",
    "        \n",
    "        for i in range(prefer.shape[0]):\n",
    "            self.prefer_dict[prefer[i]] = [12*(prefer.shape[0] - i), -6]\n",
    "    \n",
    "    \n",
    "    def add_gifts_prefer(self, giftid, score):\n",
    "        \n",
    "        if giftid in self.prefer_dict.keys():\n",
    "            self.prefer_dict[giftid][1] = 6*score\n",
    "        else:\n",
    "            self.prefer_dict[giftid] = [-6, 6*score]\n",
    "        \n",
    "        return None\n",
    "        \n",
    "    \n",
    "    def happiness(self, giftid):\n",
    "        \n",
    "        return self.prefer_dict.get(giftid, [-6, -6])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T05:19:38.895343Z",
     "start_time": "2018-12-19T05:19:38.885916Z"
    }
   },
   "outputs": [],
   "source": [
    "#双胞胎\n",
    "class Child_twin(object):\n",
    "    \n",
    "    def __init__(self, idx, prefer1, prefer2):\n",
    "        \n",
    "        self.idx = idx\n",
    "        self.prefer_dict = dict()\n",
    "        \n",
    "        for p in list(set(list(prefer1) + list(prefer2))):\n",
    "            score = 0\n",
    "            if p in list(prefer1):\n",
    "                score += 2*(100 - list(prefer1).index(p))\n",
    "            else:\n",
    "                score -= 1\n",
    "            if p in list(prefer2):\n",
    "                score += 2*(100 - list(prefer2).index(p))\n",
    "            else:\n",
    "                score -= 1\n",
    "            self.prefer_dict[p] = [3*score, -6]\n",
    "    \n",
    "    \n",
    "    def add_gifts_prefer(self, giftid, score):\n",
    "        \n",
    "        if giftid in self.prefer_dict.keys():\n",
    "            self.prefer_dict[giftid][1] = 3*score\n",
    "        else:\n",
    "            self.prefer_dict[giftid] = [-6, 3*score]\n",
    "        \n",
    "        return None\n",
    "        \n",
    "    \n",
    "    def happiness(self, giftid):\n",
    "        \n",
    "        return self.prefer_dict.get(giftid, [-6, -6])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T05:22:30.354214Z",
     "start_time": "2018-12-19T05:22:30.341819Z"
    }
   },
   "outputs": [],
   "source": [
    "#三胞胎\n",
    "class Child_triplet(object):\n",
    "    \"\"\"\n",
    "对于三胞胎，三个人要作为整体考虑\n",
    "param idx:child id \n",
    "param prefer1:三胞胎中第一个孩子偏爱的礼物\n",
    "param prefer2:三胞胎中第二个孩子偏爱的礼物\n",
    "param prefer3:三胞胎中第三个孩子偏爱的礼物\n",
    "    \"\"\"\n",
    "    def __init__(self, idx, prefer1, prefer2, prefer3):       \n",
    "        self.idx = idx\n",
    "        self.prefer_dict = dict()\n",
    "        #三胞胎三个人，有三组不同的喜欢的礼物，所以对于三胞胎set(list(prefer1) + list(prefer2) + list(prefer3))肯定大于100\n",
    "        for p in list(set(list(prefer1) + list(prefer2) + list(prefer3))):\n",
    "            score = 0\n",
    "            #对于三胞胎中的第一个人，偏爱有各种礼物的得分\n",
    "            if p in list(prefer1):\n",
    "                score += 2*(100 - list(prefer1).index(p))\n",
    "            else:\n",
    "                score -= 1\n",
    "            #对于三胞胎中的第二个人\n",
    "            if p in list(prefer2):\n",
    "                score += 2*(100 - list(prefer2).index(p))\n",
    "            else:\n",
    "                score -= 1\n",
    "            #对于三胞胎中的第三个人\n",
    "            if p in list(prefer3):\n",
    "                score += 2*(100 - list(prefer3).index(p))\n",
    "            else:\n",
    "                score -= 1\n",
    "            #这个是在干啥？\n",
    "            self.prefer_dict[p] = [2*score, -6]\n",
    "    \n",
    "    \n",
    "    def add_gifts_prefer(self, giftid, score):\n",
    "        \n",
    "        #最佳匹配\n",
    "        if giftid in self.prefer_dict.keys():\n",
    "            self.prefer_dict[giftid][1] = 2*score\n",
    "        else:\n",
    "            self.prefer_dict[giftid] = [-6, 2*score]\n",
    "        \n",
    "        return None\n",
    "        \n",
    "    \n",
    "    def happiness(self, giftid):\n",
    "        \n",
    "        return self.prefer_dict.get(giftid, [-6, -6])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-18T07:46:37.304188Z",
     "start_time": "2018-12-18T07:46:37.297973Z"
    }
   },
   "source": [
    "#### 得到一个孩子喜欢的礼物\n",
    "gift_pref[index]\n",
    "#### 三胞胎孩子的礼物\n",
    "Child_triplet(0, gift_pref[0], gift_pref[1], gift_pref[2])\n",
    "#### 双胞胎孩子的礼物\n",
    "Child_twin(5001, gift_pref[5001], gift_pref[5002])\n",
    "#### 普通孩子\n",
    "Child(45001, gift_pref[45001])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-18T08:18:35.781770Z",
     "start_time": "2018-12-18T08:18:35.752136Z"
    }
   },
   "source": [
    "### 小例子解释作者是在干啥\n",
    "```python\n",
    "C=[]\n",
    "C.append(Child_triplet(0, gift_pref[0], gift_pref[1], gift_pref[2]))\n",
    "C.append(Child_twin(5001, gift_pref[5001], gift_pref[5002]))\n",
    "C.append(Child(45001, gift_pref[45001]))\n",
    "\n",
    "#由于index=0的孩子是三胞胎，因此它偏爱的礼物数是大于100的,从下面的几个条语句可以看出，0号孩子也有偏爱0号礼物的。\n",
    "#虽然它不在0号孩子偏爱的礼物中，但它在1号孩子偏爱的礼物中。\n",
    "print(np.where(gift_pref[0]==0))\n",
    "print(np.where(gift_pref[1]==0))\n",
    "print(gift_pref[1][40])\n",
    "print(np.where(gift_pref[2]==0))\n",
    "(array([], dtype=int64),)\n",
    "(array([40]),)\n",
    "0\n",
    "(array([], dtype=int64),)\n",
    "#第0个孩子匹配第0个礼物的得分（这样存储的有个问题如果没有礼物则会直接报错）\n",
    "C[0].prefer_dict[0]\n",
    "[236, -6]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T05:38:08.640548Z",
     "start_time": "2018-12-19T05:22:41.716234Z"
    }
   },
   "outputs": [],
   "source": [
    "Children = []\n",
    "for i in range(0, 5001, 3):\n",
    "    Children.append(Child_triplet(i, gift_pref[i], gift_pref[i+1], gift_pref[i+2]))\n",
    "    Children.append(Child_triplet(i+1, gift_pref[i], gift_pref[i+1], gift_pref[i+2]))\n",
    "    Children.append(Child_triplet(i+2, gift_pref[i], gift_pref[i+1], gift_pref[i+2]))\n",
    "for i in range(5001, 45001, 2):\n",
    "    Children.append(Child_twin(i, gift_pref[i], gift_pref[i+1]))\n",
    "    Children.append(Child_twin(i+1, gift_pref[i], gift_pref[i+1]))\n",
    "Children = Children + [Child(i, gift_pref[i]) for i in range(45001, 1000000)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T06:07:20.374438Z",
     "start_time": "2018-12-19T05:51:35.957568Z"
    }
   },
   "outputs": [],
   "source": [
    "for j in range(1000):\n",
    "    #每类礼物更偏爱的孩子\n",
    "    cf = child_pref[j]\n",
    "    done_list = []\n",
    "    for i in range(cf.shape[0]):\n",
    "        #同一礼物如果是三胞胎则以三胞胎中最先出现的为主。\n",
    "        if cf[i] <= 5000 and cf[i] not in done_list:\n",
    "            if cf[i] % 3 == 0:\n",
    "                cid1 = cf[i]\n",
    "                cid2 = cf[i] + 1\n",
    "                cid3 = cf[i] + 2\n",
    "                done_list.append(cid2)\n",
    "                done_list.append(cid3)\n",
    "            elif cf[i] % 3 == 1:\n",
    "                cid1 = cf[i] - 1\n",
    "                cid2 = cf[i]\n",
    "                cid3 = cf[i] + 1\n",
    "                done_list.append(cid1)\n",
    "                done_list.append(cid3)\n",
    "            else:\n",
    "                cid1 = cf[i] - 2\n",
    "                cid2 = cf[i] - 1\n",
    "                cid3 = cf[i]\n",
    "                done_list.append(cid1)\n",
    "                done_list.append(cid2)\n",
    "            if cid1 in list(cf):\n",
    "                score_ = 2*(cf.shape[0] - list(cf).index(cid1))\n",
    "            else:\n",
    "                score_ = -1\n",
    "            if cid2 in list(cf):\n",
    "                score_ += 2*(cf.shape[0] - list(cf).index(cid2))\n",
    "            else:\n",
    "                score_ += -1\n",
    "            if cid3 in list(cf):\n",
    "                score_ += 2*(cf.shape[0] - list(cf).index(cid3))\n",
    "            else:\n",
    "                score_ += -1\n",
    "            Children[cid1].add_gifts_prefer(j, score_)\n",
    "            Children[cid2].add_gifts_prefer(j, score_)\n",
    "            Children[cid3].add_gifts_prefer(j, score_)\n",
    "            #如果是双胞胎\n",
    "            #以双胞胎最先出现的为主\n",
    "        elif cf[i] <= 45000 and cf[i] not in done_list:\n",
    "            if cf[i] % 2 == 1:\n",
    "                cid1 = cf[i]\n",
    "                cid2 = cf[i] + 1\n",
    "                done_list.append(cid2)\n",
    "            else:\n",
    "                cid1 = cf[i] - 1\n",
    "                cid2 = cf[i]\n",
    "                done_list.append(cid1)\n",
    "            if cid1 in list(cf):\n",
    "                score_ = 2*(cf.shape[0] - list(cf).index(cid1))\n",
    "            else:\n",
    "                score_ = -1\n",
    "            if cid2 in list(cf):\n",
    "                score_ += 2*(cf.shape[0] - list(cf).index(cid2))\n",
    "            else:\n",
    "                score_ += -1\n",
    "            Children[cid1].add_gifts_prefer(j, score_)\n",
    "            Children[cid2].add_gifts_prefer(j, score_)\n",
    "            #如果是普通孩子\n",
    "        elif cf[i] > 45000:\n",
    "            Children[cf[i]].add_gifts_prefer(j, 2*(cf.shape[0] - i))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 到目前为止对Children中的操作实际为：\n",
    "记$C_i$表示第i个孩子，$G_j$表示第$j$个礼物，$H_{i,j}$表示第$i$个孩子偏爱第$j$个礼物的得分，$H_{j,i}$表示第j个礼物更偏爱第$i$个孩子的得分，prefer_dict[j]代表的是第i个孩子与第j个礼物之间的相互偏爱得分$[H_{i,j},H_{j,i}]$，其中只有一个得分值存在则对于第i个孩子prefer_dict[j]存在\n",
    "- 1.从孩子偏爱的礼物出发，可求出存在的$H_{i,j}$,此时第i个孩子的prefer_dict[j]=$[H_{i,j},-6]$\n",
    "- 2.从礼物偏爱的孩子出发，可求出存在的$H_{j,i}$,此时如果prefer_dict[j]已经存在$[H_{i,j},-6]$，则直接将-6替换为$H_{j,i}$,否则开辟新的prefer_dict[j]=$[-6，H_{j,i}]$\n",
    "**综上prefer_dict存储的是双方中只要有一方有偏爱的得分。**<mark>如果都没有，则根本不存在，孩子i对应礼物j的prefer_dict[j]</mark>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T10:26:17.694269Z",
     "start_time": "2018-12-19T10:26:17.251414Z"
    }
   },
   "source": [
    "### MinCostFlow简介\n",
    "<a href='https://developers.google.com/optimization/flow/mincostflow'>详情</a>\n",
    "![avatar](MinCostFlow.png)\n",
    "```python\n",
    "# \"\"\"From Bradley, Hax, and Magnanti, 'Applied Mathematical Programming', figure 8.1.\"\"\"\n",
    "\n",
    "from __future__ import print_function\n",
    "from ortools.graph import pywrapgraph\n",
    "\n",
    "def main():\n",
    "  \"\"\"MinCostFlow simple interface example.\"\"\"\n",
    "\n",
    "  # Define four parallel arrays: start_nodes, end_nodes, capacities, and unit costs\n",
    "  # between each pair. For instance, the arc from node 0 to node 1 has a\n",
    "  # capacity of 15 and a unit cost of 4.\n",
    "\n",
    "  start_nodes = [ 0, 0,  1, 1,  1,  2, 2,  3, 4]\n",
    "  end_nodes   = [ 1, 2,  2, 3,  4,  3, 4,  4, 2]\n",
    "  capacities  = [15, 8, 20, 4, 10, 15, 4, 20, 5]\n",
    "  unit_costs  = [ 4, 4,  2, 2,  6,  1, 3,  2, 3]\n",
    "\n",
    "  # Define an array of supplies at each node.\n",
    "\n",
    "  supplies = [20, 0, 0, -5, -15]\n",
    "\n",
    "\n",
    "  # Instantiate a SimpleMinCostFlow solver.\n",
    "  min_cost_flow = pywrapgraph.SimpleMinCostFlow()\n",
    "\n",
    "  # Add each arc.\n",
    "  for i in range(0, len(start_nodes)):\n",
    "    min_cost_flow.AddArcWithCapacityAndUnitCost(start_nodes[i], end_nodes[i],\n",
    "                                                capacities[i], unit_costs[i])\n",
    "\n",
    "  # Add node supplies.\n",
    "\n",
    "  for i in range(0, len(supplies)):\n",
    "    min_cost_flow.SetNodeSupply(i, supplies[i])\n",
    "\n",
    "\n",
    "  # Find the minimum cost flow between node 0 and node 4.\n",
    "  if min_cost_flow.Solve() == min_cost_flow.OPTIMAL:\n",
    "    print('Minimum cost:', min_cost_flow.OptimalCost())\n",
    "    print('')\n",
    "    print('  Arc    Flow / Capacity  Cost')\n",
    "    for i in range(min_cost_flow.NumArcs()):\n",
    "      cost = min_cost_flow.Flow(i) * min_cost_flow.UnitCost(i)\n",
    "      print('%1s -> %1s   %3s  / %3s       %3s' % (\n",
    "          min_cost_flow.Tail(i),\n",
    "          min_cost_flow.Head(i),\n",
    "          min_cost_flow.Flow(i),\n",
    "          min_cost_flow.Capacity(i),\n",
    "          cost))\n",
    "  else:\n",
    "    print('There was an issue with the min cost flow input.')\n",
    "\n",
    "if __name__ == '__main__':\n",
    "  main()\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 先把下面的一大段代码分成小例子解释作者在干嘛，以三胞胎的为例（这个如果看懂了，说明上面的代码都懂了）\n",
    "```python\n",
    "min_cost_flow_e = pywrapgraph.SimpleMinCostFlow()\n",
    "\n",
    "W_CHILD_e = 10000\n",
    "W_GIFTS_e = 0\n",
    "\n",
    "start_nodes_e = []\n",
    "end_nodes_e = []\n",
    "capacities_e = []\n",
    "unit_costs_e = []\n",
    "# triplets以0号三胞胎为例：start_nodes_e->end_nodes_e实际是从礼物指向孩子（gift->child)\n",
    "for i in range(0, 3, 3):\n",
    "    for g in Children[i].prefer_dict.keys():\n",
    "        #与礼物相关，只是礼物编号加了1000000\n",
    "        start_nodes_e.append(1000000+g)\n",
    "        #孩子编号\n",
    "        end_nodes_e.append(i)\n",
    "        #三胞胎礼物都一样\n",
    "        capacities.append(3)\n",
    "        #没有什么特别的处理，就是把单方面没有的归0了而已\n",
    "        unit_costs.append(-W_CHILD*(Children[i].prefer_dict[g][0] + 6)-W_GIFTS*(Children[i].prefer_dict[g][1] + 6))\n",
    "```\n",
    "<mark>执行下面两段代码，就很清楚数据来源了：</mark>\n",
    "```python\n",
    "#triplets\n",
    "print(len(start_nodes_e))\n",
    "print(len(list(Children[0].prefer_dict.keys())))\n",
    "270\n",
    "270\n",
    "```\n",
    "\n",
    "\n",
    "```python\n",
    "start_nodes_value=[m+1000000 for m in list(Children[0].prefer_dict.keys())]\n",
    "start_nodes_value==start_nodes_e\n",
    "True\n",
    "```\n",
    "\n",
    "#### <mark>可以改进的：</mark>\n",
    "- prefer_dict[g][0]、prefer_dict[g][1]两个Happiness Score它是简单的相加"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T06:07:31.708452Z",
     "start_time": "2018-12-19T06:07:30.554057Z"
    }
   },
   "outputs": [],
   "source": [
    "from ortools.graph import pywrapgraph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T06:09:06.552698Z",
     "start_time": "2018-12-19T06:09:06.547774Z"
    }
   },
   "outputs": [],
   "source": [
    "W_CHILD = 10000\n",
    "W_GIFTS = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T06:09:08.096990Z",
     "start_time": "2018-12-19T06:09:08.092871Z"
    }
   },
   "outputs": [],
   "source": [
    "min_cost_flow_1 = pywrapgraph.SimpleMinCostFlow()\n",
    "\n",
    "start_nodes = []\n",
    "end_nodes = []\n",
    "capacities = []\n",
    "unit_costs = []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T06:25:43.935647Z",
     "start_time": "2018-12-19T06:09:37.275231Z"
    }
   },
   "outputs": [],
   "source": [
    "#构建StartNodes\n",
    "# triplets\n",
    "for i in range(0, 5001, 3):\n",
    "    for g in Children[i].prefer_dict.keys():\n",
    "        start_nodes.append(1000000+g)\n",
    "        end_nodes.append(i)\n",
    "        capacities.append(3)\n",
    "        unit_costs.append(-W_CHILD*(Children[i].prefer_dict[g][0] + 6)-W_GIFTS*(Children[i].prefer_dict[g][1] + 6))\n",
    "        \n",
    "# triplets\n",
    "for i in range(5001, 45001, 2):\n",
    "    for g in Children[i].prefer_dict.keys():\n",
    "        start_nodes.append(1000000+g)\n",
    "        end_nodes.append(i)\n",
    "        capacities.append(2)\n",
    "        unit_costs.append(-W_CHILD*(Children[i].prefer_dict[g][0] + 6)-W_GIFTS*(Children[i].prefer_dict[g][1] + 6))\n",
    "        \n",
    "# other children\n",
    "for i in range(45001, 1000000):\n",
    "    \n",
    "    for g in Children[i].prefer_dict.keys():\n",
    "        start_nodes.append(1000000+g)\n",
    "        end_nodes.append(i)\n",
    "        capacities.append(1)\n",
    "        unit_costs.append(-W_CHILD*(Children[i].prefer_dict[g][0] + 6)-W_GIFTS*(Children[i].prefer_dict[g][1] + 6))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T08:19:44.490772Z",
     "start_time": "2018-12-19T08:15:04.662892Z"
    }
   },
   "outputs": [],
   "source": [
    "#开始画图了\n",
    "# add Arc（画边，用上面的start_nodes-->end_nodes,即gift-->childern)\n",
    "# gift -> children\n",
    "for i in range(len(start_nodes)):\n",
    "    min_cost_flow_1.AddArcWithCapacityAndUnitCost(\n",
    "        int(start_nodes[i]), int(end_nodes[i]), int(capacities[i]), int(unit_costs[i])\n",
    "    )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T08:47:18.308033Z",
     "start_time": "2018-12-19T08:47:16.664388Z"
    }
   },
   "outputs": [],
   "source": [
    "# 1001000结点为孩子节点的集合结点，添加从每个收到礼物的孩子结点到此节点的一条路径，capacity=礼物数，cost为0,Good!\n",
    "# children -> 1001000 : collection(孩子到终止节点)\n",
    "\n",
    "for i in range(0, 5001, 3):\n",
    "    min_cost_flow_1.AddArcWithCapacityAndUnitCost(\n",
    "        int(i), int(1001000), int(3), int(0)\n",
    "    )\n",
    "for i in range(5001, 45001, 2):\n",
    "    min_cost_flow_1.AddArcWithCapacityAndUnitCost(\n",
    "        int(i), int(1001000), int(2), int(0)\n",
    "    )\n",
    "for i in range(45001, 1000000):\n",
    "    min_cost_flow_1.AddArcWithCapacityAndUnitCost(\n",
    "        int(i), int(1001000), int(1), int(0)\n",
    "    )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T08:54:24.287181Z",
     "start_time": "2018-12-19T08:54:24.270658Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "101550693"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#gift结点到终止节点capacity=1000 and cost=0\n",
    "# gift -> 1001001 : dust_gift\n",
    "# 1001001结点为礼物结点的汇总节点，添加从每个礼物结点到汇总节点的容量为1000花费为0的通路\n",
    "for i in range(1000):\n",
    "    min_cost_flow_1.AddArcWithCapacityAndUnitCost(\n",
    "        int(1000000+i), int(1001001), int(1000), int(0)\n",
    "    )\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 1001001 -> 1001000 : dust_path\n",
    "# 添加从开始结点的汇总节点到结束结点的汇总节点的容量为1000000花费为0的通路\n",
    "min_cost_flow_1.AddArcWithCapacityAndUnitCost(\n",
    "        int(1001001), int(1001000), int(1000000), int(0)\n",
    "    )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T08:56:55.331776Z",
     "start_time": "2018-12-19T08:56:55.321590Z"
    }
   },
   "outputs": [],
   "source": [
    "# add gift Supply\n",
    "for i in range(1000):\n",
    "    min_cost_flow_1.SetNodeSupply(int(1000000+i), int(1000))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T08:57:32.319378Z",
     "start_time": "2018-12-19T08:57:31.310538Z"
    }
   },
   "outputs": [],
   "source": [
    "# add children Supply\n",
    "for i in range(0, 5001, 3):\n",
    "    min_cost_flow_1.SetNodeSupply(int(i), int(0))\n",
    "for i in range(5001, 45001, 2):\n",
    "    min_cost_flow_1.SetNodeSupply(int(i), int(0))\n",
    "for i in range(45001, 1000000):\n",
    "    min_cost_flow_1.SetNodeSupply(int(i), int(0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T09:02:19.631343Z",
     "start_time": "2018-12-19T09:02:19.624858Z"
    }
   },
   "outputs": [],
   "source": [
    "#孩子的终点处supply为-1000000\n",
    "min_cost_flow_1.SetNodeSupply(int(1001000), int(-1000000)) \n",
    "#gift的终点处supply为0\n",
    "min_cost_flow_1.SetNodeSupply(int(1001001), int(0)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T09:11:11.487807Z",
     "start_time": "2018-12-19T09:04:36.174571Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.random.seed(71)\n",
    "min_cost_flow_1.Solve()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T09:22:17.411735Z",
     "start_time": "2018-12-19T09:18:00.460932Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10000 0 11739596260 161786 1617929090195337305936165431656\n",
      "0.9363015568260054\n"
     ]
    }
   ],
   "source": [
    "assignment = [-1]*1000000\n",
    "twins_differ = []\n",
    "triplets_differ = []\n",
    "\n",
    "for i in range(min_cost_flow_1.NumArcs()):\n",
    "    if min_cost_flow_1.Flow(i) != 0 and min_cost_flow_1.Head(i) < 1000000:\n",
    "        c = min_cost_flow_1.Head(i)\n",
    "        g = min_cost_flow_1.Tail(i)\n",
    "        f = min_cost_flow_1.Flow(i)\n",
    "\n",
    "        if c >= 45001:\n",
    "            assignment[c] = g - 1000000\n",
    "\n",
    "        elif c >= 5001:\n",
    "            if f == 1:\n",
    "                if assignment[c] == -1:\n",
    "                    assignment[c] = g - 1000000\n",
    "                    twins_differ.append([c, c+1])\n",
    "                else:\n",
    "                    assignment[c+1] = g - 1000000\n",
    "            elif f == 2:\n",
    "                assignment[c] = g - 1000000\n",
    "                assignment[c+1] = g - 1000000\n",
    "        else:\n",
    "            if f == 1:\n",
    "                if assignment[c] == -1:\n",
    "                    assignment[c] = g - 1000000\n",
    "                    triplets_differ.append([c, c+1, c+2])\n",
    "                elif assignment[c+1] == -1:\n",
    "                    assignment[c+1] = g - 1000000\n",
    "                else:\n",
    "                    assignment[c+2] = g - 1000000\n",
    "            elif f == 2:\n",
    "                if assignment[c] == -1:\n",
    "                    assignment[c] = g - 1000000\n",
    "                    assignment[c+1] = g - 1000000\n",
    "                    triplets_differ.append([c, c+1, c+2])\n",
    "                else:\n",
    "                    assignment[c+1] = g - 1000000\n",
    "                    assignment[c+2] = g - 1000000\n",
    "            elif f == 3:\n",
    "                assignment[c] = g - 1000000\n",
    "                assignment[c+1] = g - 1000000\n",
    "                assignment[c+2] = g - 1000000\n",
    "                \n",
    "CHILD_HAPPINESS = sum([Children[i].happiness(assignment[i])[0] for i in range(1000000)])*10\n",
    "SANTA_HAPPINESS = sum([Children[i].happiness(assignment[i])[1] for i in range(1000000)])\n",
    "OBJ = CHILD_HAPPINESS**3 + SANTA_HAPPINESS**3\n",
    "print(W_CHILD, W_GIFTS, CHILD_HAPPINESS, SANTA_HAPPINESS, OBJ)\n",
    "print(OBJ / (12000000000**3))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T09:24:14.759933Z",
     "start_time": "2018-12-19T09:24:14.739472Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(76, 13)"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(twins_differ), len(triplets_differ)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T09:25:37.791792Z",
     "start_time": "2018-12-19T09:25:37.333176Z"
    }
   },
   "outputs": [],
   "source": [
    "# well assigned twins and triplets\n",
    "well_assigned = []\n",
    "for i in range(0, 5001, 3):\n",
    "    if assignment[i] == assignment[i+1] and assignment[i] == assignment[i+2]:\n",
    "        well_assigned.append(i)\n",
    "        well_assigned.append(i+1)\n",
    "        well_assigned.append(i+2)\n",
    "for i in range(5001, 45001, 2):\n",
    "    if assignment[i] == assignment[i+1]:\n",
    "        well_assigned.append(i)\n",
    "        well_assigned.append(i+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T09:25:40.712141Z",
     "start_time": "2018-12-19T09:25:40.701071Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "44810"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(well_assigned)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T09:26:41.050167Z",
     "start_time": "2018-12-19T09:26:41.016503Z"
    }
   },
   "outputs": [],
   "source": [
    "Gifts_left = [1000 for _ in range(1000)]\n",
    "for i in well_assigned:\n",
    "    if assignment[i] != -1:\n",
    "        Gifts_left[assignment[i]] -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-19T09:26:56.588815Z",
     "start_time": "2018-12-19T09:26:56.578791Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "958921"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(Gifts_left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#剩下的没匹配的gifts较少时的处理\n",
    "gifts_for_trips = [628, 180, 141, 496, 148, 983, 707, 409]\n",
    "gifts_for_twins = [4, 0, 0, 4, 4, 932, 2, 4]\n",
    "for i in range(8):\n",
    "    gifts_for_trips[i] -= gifts_for_twins[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "gifts_left_list = []\n",
    "for i in range(gifts_for_trips[0]):\n",
    "    gifts_left_list.append(118)\n",
    "for i in range(gifts_for_trips[1]):\n",
    "    gifts_left_list.append(240)\n",
    "for i in range(gifts_for_trips[2]):\n",
    "    gifts_left_list.append(272)\n",
    "for i in range(gifts_for_trips[3]):\n",
    "    gifts_left_list.append(320)\n",
    "for i in range(gifts_for_trips[4]):\n",
    "    gifts_left_list.append(389)\n",
    "for i in range(gifts_for_trips[5]):\n",
    "    gifts_left_list.append(494)\n",
    "for i in range(gifts_for_trips[6]):\n",
    "    gifts_left_list.append(671)\n",
    "for i in range(gifts_for_trips[7]):\n",
    "    gifts_left_list.append(998)\n",
    "    \n",
    "for i in range(gifts_for_twins[0]):\n",
    "    gifts_left_list.append(118)\n",
    "for i in range(gifts_for_twins[1]):\n",
    "    gifts_left_list.append(240)\n",
    "for i in range(gifts_for_twins[2]):\n",
    "    gifts_left_list.append(272)\n",
    "for i in range(gifts_for_twins[3]):\n",
    "    gifts_left_list.append(320)\n",
    "for i in range(gifts_for_twins[4]):\n",
    "    gifts_left_list.append(389)\n",
    "for i in range(gifts_for_twins[5]):\n",
    "    gifts_left_list.append(494)\n",
    "for i in range(gifts_for_twins[6]):\n",
    "    gifts_left_list.append(671)\n",
    "for i in range(gifts_for_twins[7]):\n",
    "    gifts_left_list.append(998)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ind = 0\n",
    "for i in range(1000000):\n",
    "    if assignment[i] == -1:\n",
    "        assignment[i] = gifts_left_list[ind]\n",
    "        ind += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "out = open('../submit/seed71_solution.csv', 'w')\n",
    "out.write('ChildId,GiftId\\n')\n",
    "for i in range(1000000):\n",
    "    out.write(str(i) + ',' + str(assignment[i]) + '\\n')\n",
    "out.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-13T13:35:32.667949Z",
     "start_time": "2018-12-13T13:35:32.661343Z"
    }
   },
   "source": [
    "#### 求最大公约数math.gcd\n",
    "```python\n",
    "# greatest common divisor of x and y\n",
    "math.gcd(319,377)\n",
    "29\n",
    "```\n",
    "- 最大公约数=A×B/最小公倍数,下面的函数实际上是求的最小公倍数\n",
    "```python\n",
    "def lcm(a, b):\n",
    "    \"\"\"Compute the lowest common multiple of a and b\"\"\"\n",
    "    # in case of large numbers, using floor division\n",
    "    return a * b // math.gcd(a, b)\n",
    "```\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-13T13:42:45.142980Z",
     "start_time": "2018-12-13T13:42:45.137651Z"
    }
   },
   "outputs": [],
   "source": [
    "def lcm(a, b):\n",
    "    \"\"\"Compute the lowest common multiple of a and b，求的是最小公倍数\"\"\"\n",
    "    # in case of large numbers, using floor division\n",
    "    return a * b // math.gcd(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# kaggle给的计算平均归一化幸福感的函数\n",
    "def avg_normalized_happiness(pred, child_pref, gift_pref):\n",
    "    \n",
    "    # check if number of each gift exceeds n_gift_quantity\n",
    "    gift_counts = Counter(elem[1] for elem in pred)\n",
    "    for count in gift_counts.values():\n",
    "        assert count <= n_gift_quantity\n",
    "                \n",
    "    # check if triplets have the same gift\n",
    "    for t1 in np.arange(0,triplets,3):\n",
    "        triplet1 = pred[t1]\n",
    "        triplet2 = pred[t1+1]\n",
    "        triplet3 = pred[t1+2]\n",
    "        # print(t1, triplet1, triplet2, triplet3)\n",
    "        assert triplet1[1] == triplet1[1] and triplet2[1] == triplet3[1]\n",
    "                \n",
    "    # check if twins have the same gift\n",
    "    for t1 in np.arange(triplets,triplets+twins,2):\n",
    "        twin1 = pred[t1]\n",
    "        twin2 = pred[t1+1]\n",
    "        # print(t1)\n",
    "        assert twin1[1] == twin2[1]\n",
    "\n",
    "    max_child_happiness = n_gift_pref * ratio_child_happiness\n",
    "    max_gift_happiness = n_child_pref * ratio_gift_happiness\n",
    "    total_child_happiness = 0\n",
    "    total_gift_happiness = np.zeros(n_gift_type)\n",
    "    \n",
    "    for row in pred:\n",
    "        child_id = row[0]\n",
    "        gift_id = row[1]\n",
    "        \n",
    "        # check if child_id and gift_id exist\n",
    "        assert child_id < n_children\n",
    "        assert gift_id < n_gift_type\n",
    "        assert child_id >= 0 \n",
    "        assert gift_id >= 0\n",
    "        child_happiness = (n_gift_pref - np.where(gift_pref[child_id]==gift_id)[0]) * ratio_child_happiness\n",
    "        if not child_happiness:\n",
    "            child_happiness = -1\n",
    "\n",
    "        gift_happiness = ( n_child_pref - np.where(child_pref[gift_id]==child_id)[0]) * ratio_gift_happiness\n",
    "        if not gift_happiness:\n",
    "            gift_happiness = -1\n",
    "\n",
    "        total_child_happiness += child_happiness\n",
    "        total_gift_happiness[gift_id] += gift_happiness\n",
    "    \n",
    "    print('normalized child happiness=',float(total_child_happiness)/(float(n_children)*float(max_child_happiness)) , \\\n",
    "        ', normalized gift happiness',np.mean(total_gift_happiness) / float(max_gift_happiness*n_gift_quantity))\n",
    "\n",
    "    # to avoid float rounding error\n",
    "    # find common denominator\n",
    "    # NOTE: I used this code to experiment different parameters, so it was necessary to get the multiplier\n",
    "    # Note: You should hard-code the multipler to speed up, now that the parameters are finalized\n",
    "    denominator1 = n_children*max_child_happiness\n",
    "    denominator2 = n_gift_quantity*max_gift_happiness*n_gift_type\n",
    "    common_denom = lcm(denominator1, denominator2)\n",
    "    multiplier = common_denom / denominator1\n",
    "\n",
    "    # # usually denom1 > demon2\n",
    "    return float(math.pow(total_child_happiness*multiplier,3) + math.pow(np.sum(total_gift_happiness),3)) / float(math.pow(common_denom,3))\n",
    "    # return math.pow(float(total_child_happiness)/(float(n_children)*float(max_child_happiness)),2) + math.pow(np.mean(total_gift_happiness) / float(max_gift_happiness*n_gift_quantity),2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 计算给出的随机提交结果的幸福感\n",
    "random_sub = pd.read_csv('../input/sample_submission_random_v2.csv').values.tolist()\n",
    "print(avg_normalized_happiness(random_sub, child_pref, gift_pref))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
